A convolutional code has been widely used in many communication systems as a forward error correction (FEC) method. The Viterbi decoding algorithm is optimum for decoding of the received data, which is transmitted after convolutional encoding.
The decoding speed of the Viterbi decoding algorithm is limited by the iteration bound because the add-compare-select (ACS) recursion in the Viterbi decoding algorithm contains feedback loops. A look-ahead technique, which combines several trellis steps into one trellis step in time sequence, has been used for breaking the iteration bound of the Viterbi decoding algorithm. In the look-ahead technique, the combined branch metrics can be computed outside of the ACS recursion (referred as ACS precomputation). This allows the ACS loop to be pipelined or computed in parallel. Thereby, the decoding throughput rate can be increased. This is an advantage of the look-ahead technique. The look-ahead step (M) for a given throughput rate is obtained as the desired throughput rate divided by the ACS recursion clock rate since the overall decoding speed is limited by the allowed maximum frequency of the ACS recursion clock. Therefore, large number of look-ahead steps or high parallelism factor is needed to implement high-throughput rate Viterbi decoding.
In this invention, the ACS computation without the addition of the previous state metrics (or path metrics or accumulated branch metrics) is referred as the ACS precomputation to distinguish it from the ACS recursion, which adds the previous state metrics to the look-ahead branch metrics used for state update operation inside the feedback loop.
The main drawback of the traditional M-step look-ahead technique is that it leads to long latency for look-ahead ACS precomputation, especially when very large number of look-ahead steps is required. When the ACS precomputation unit is implemented as a pipeline structure, the ACS precomputation latency of the traditional M-step look-ahead method increases linearly with respect to the look-ahead step.
In this invention, an alternate approach is considered where the method of combining trellis steps is changed such that the inherent decoding latency can be. It combines K-trellis (where K is the encoder constraint length) steps into one trellis-step and then combines resulting sub-trellises in a layered manner (refereed as K-nested layered look-ahead, LLA). In this approach, the ACS precomputation latency can be significantly decased for high order look-ahead cases as long as the level of parallelism, M, is a multiple of the encoder constraint length, K.
The practical use of this invention is extremely important for implementation of high speed, i.e., 5 or 10 Gb/s, serializer-deserializer (SERDES), where the latency constraint is critical. The SERDES can be used in 10 Gb/s fiber channel synchronous optical network (SONET) or 10 Gb/s Ethernet local area network (LAN), etc. The low-latency Viterbi detector based on this invention may also be used in high density optical or magnetic storage y such as digital video disk (DVD) and hard disk drive (HDD) systems.